package com.eistert.java.algorithm.template;


import java.util.Stack;

/**
 * @Description: binary tree traversal implementation code template
 * @Author: ai
 * @create: 2023-04-16 12:10
 */
public class BinaryTreeTraversalTemplate {

    /**
     * definitation for binary tree node
     */
    private class Node<E> {

        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }

    }

    /**
     * 二叉树 前序遍历
     */
    // 前序遍历以node为根的二分搜索树, 递归算法
    private void preOrder(Node node) {

        if (node == null)
            return;

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }


    /**
     * 二叉树 中序遍历
     */

    private void inOrder(Node node) {

        if (node == null)
            return;

        preOrder(node.left);
        System.out.println(node.e);
        preOrder(node.right);
    }


    /**
     * 二叉树 后序遍历
     */

    private void postOrder(Node node) {

        if (node == null)
            return;

        preOrder(node.left);
        preOrder(node.right);
        System.out.println(node.e);
    }


    /**
     * 二叉树 层序遍历
     */
    // 二分搜索树的非递归前序遍历
    public void preOrderNR(Node root) {

        if (root == null)
            return;

        Stack<Node> stack = new Stack<>(); // 先进后出
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.e);

            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }
    }

}
